/**
 * Sort a linked list using insertion sort.
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* insertionSortList(struct ListNode* head) {
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *pre = dummy, *cur = head, *tmp;
    dummy->next = NULL;
    if(!head || !head->next) return head;
    while(cur) {
        while(pre->next && cur->val > pre->next->val)
            pre = pre->next;
        tmp = cur;
        cur = cur->next;
        tmp->next = pre->next;
        pre->next = tmp;
        pre = dummy;
    }
    return dummy->next;
}